Handling long targets and errors in sequencing by hybridization.
Identifieur interne : 003215 ( Main/Exploration ); précédent : 003214; suivant : 003216Handling long targets and errors in sequencing by hybridization.
Auteurs : Eran Halperin [États-Unis] ; Shay Halperin ; Tzvika Hartman ; Ron ShamirSource :
- Journal of computational biology : a journal of computational molecular cell biology [ 1066-5277 ] ; 2003.
Descripteurs français
- KwdFr :
- MESH :
English descriptors
- KwdEn :
- MESH :
Abstract
Sequencing by hybridization (SBH) is a DNA sequencing technique, in which the sequence is reconstructed using its k-mer content. This content, which is called the spectrum of the sequence, is obtained by hybridization to a universal DNA array. Standard universal arrays contain all k-mers for some fixed k, typically 8 to 10. Currently, in spite of its promise and elegance, SBH is not competitive with standard gel-based sequencing methods. This is due to two main reasons: lack of tools to handle realistic levels of hybridization errors and an inherent limitation on the length of uniquely reconstructible sequence by standard universal arrays. In this paper, we deal with both problems. We introduce a simple polynomial reconstruction algorithm which can be applied to spectra from standard arrays and has provable performance in the presence of both false negative and false positive errors. We also propose a novel design of chips containing universal bases that differs from the one proposed by Preparata et al. (1999). We give a simple algorithm that uses spectra from such chips to reconstruct with high probability random sequences of length lower only by a squared log factor compared to the information theoretic bound. Our algorithm is very robust to errors and has a provable performance even if there are both false negative and false positive errors. Simulations indicate that its sensitivity to errors is also very small in practice.
DOI: 10.1089/10665270360688138
PubMed: 12935339
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream PubMed, to step Corpus: 002439
- to stream PubMed, to step Curation: 002439
- to stream PubMed, to step Checkpoint: 002319
- to stream Ncbi, to step Merge: 000210
- to stream Ncbi, to step Curation: 000210
- to stream Ncbi, to step Checkpoint: 000210
- to stream Main, to step Merge: 003249
- to stream Main, to step Curation: 003215
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Handling long targets and errors in sequencing by hybridization.</title><author><name sortKey="Halperin, Eran" sort="Halperin, Eran" uniqKey="Halperin E" first="Eran" last="Halperin">Eran Halperin</name><affiliation wicri:level="2"><nlm:affiliation>CS Division, Soda Hall, University of California at Berkeley, Berkeley, CA 94720-1776, USA.</nlm:affiliation><country xml:lang="fr">États-Unis</country><wicri:regionArea>CS Division, Soda Hall, University of California at Berkeley, Berkeley, CA 94720-1776</wicri:regionArea><placeName><region type="state">Californie</region></placeName></affiliation></author><author><name sortKey="Halperin, Shay" sort="Halperin, Shay" uniqKey="Halperin S" first="Shay" last="Halperin">Shay Halperin</name></author><author><name sortKey="Hartman, Tzvika" sort="Hartman, Tzvika" uniqKey="Hartman T" first="Tzvika" last="Hartman">Tzvika Hartman</name></author><author><name sortKey="Shamir, Ron" sort="Shamir, Ron" uniqKey="Shamir R" first="Ron" last="Shamir">Ron Shamir</name></author></titleStmt><publicationStmt><idno type="wicri:source">PubMed</idno><date when="2003">2003</date><idno type="RBID">pubmed:12935339</idno><idno type="pmid">12935339</idno><idno type="doi">10.1089/10665270360688138</idno><idno type="wicri:Area/PubMed/Corpus">002439</idno><idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Corpus" wicri:corpus="PubMed">002439</idno><idno type="wicri:Area/PubMed/Curation">002439</idno><idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Curation">002439</idno><idno type="wicri:Area/PubMed/Checkpoint">002319</idno><idno type="wicri:explorRef" wicri:stream="Checkpoint" wicri:step="PubMed">002319</idno><idno type="wicri:Area/Ncbi/Merge">000210</idno><idno type="wicri:Area/Ncbi/Curation">000210</idno><idno type="wicri:Area/Ncbi/Checkpoint">000210</idno><idno type="wicri:doubleKey">1066-5277:2003:Halperin E:handling:long:targets</idno><idno type="wicri:Area/Main/Merge">003249</idno><idno type="wicri:Area/Main/Curation">003215</idno><idno type="wicri:Area/Main/Exploration">003215</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Handling long targets and errors in sequencing by hybridization.</title><author><name sortKey="Halperin, Eran" sort="Halperin, Eran" uniqKey="Halperin E" first="Eran" last="Halperin">Eran Halperin</name><affiliation wicri:level="2"><nlm:affiliation>CS Division, Soda Hall, University of California at Berkeley, Berkeley, CA 94720-1776, USA.</nlm:affiliation><country xml:lang="fr">États-Unis</country><wicri:regionArea>CS Division, Soda Hall, University of California at Berkeley, Berkeley, CA 94720-1776</wicri:regionArea><placeName><region type="state">Californie</region></placeName></affiliation></author><author><name sortKey="Halperin, Shay" sort="Halperin, Shay" uniqKey="Halperin S" first="Shay" last="Halperin">Shay Halperin</name></author><author><name sortKey="Hartman, Tzvika" sort="Hartman, Tzvika" uniqKey="Hartman T" first="Tzvika" last="Hartman">Tzvika Hartman</name></author><author><name sortKey="Shamir, Ron" sort="Shamir, Ron" uniqKey="Shamir R" first="Ron" last="Shamir">Ron Shamir</name></author></analytic><series><title level="j">Journal of computational biology : a journal of computational molecular cell biology</title><idno type="ISSN">1066-5277</idno><imprint><date when="2003" type="published">2003</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Computational Biology (methods)</term><term>Data Interpretation, Statistical</term><term>Oligonucleotide Array Sequence Analysis (methods)</term><term>Sequence Analysis, DNA (methods)</term></keywords><keywords scheme="KwdFr" xml:lang="fr"><term>Analyse de séquence d'ADN ()</term><term>Biologie informatique ()</term><term>Interprétation statistique de données</term><term>Séquençage par oligonucléotides en batterie ()</term></keywords><keywords scheme="MESH" qualifier="methods" xml:lang="en"><term>Computational Biology</term><term>Oligonucleotide Array Sequence Analysis</term><term>Sequence Analysis, DNA</term></keywords><keywords scheme="MESH" xml:lang="en"><term>Data Interpretation, Statistical</term></keywords><keywords scheme="MESH" xml:lang="fr"><term>Analyse de séquence d'ADN</term><term>Biologie informatique</term><term>Interprétation statistique de données</term><term>Séquençage par oligonucléotides en batterie</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Sequencing by hybridization (SBH) is a DNA sequencing technique, in which the sequence is reconstructed using its k-mer content. This content, which is called the spectrum of the sequence, is obtained by hybridization to a universal DNA array. Standard universal arrays contain all k-mers for some fixed k, typically 8 to 10. Currently, in spite of its promise and elegance, SBH is not competitive with standard gel-based sequencing methods. This is due to two main reasons: lack of tools to handle realistic levels of hybridization errors and an inherent limitation on the length of uniquely reconstructible sequence by standard universal arrays. In this paper, we deal with both problems. We introduce a simple polynomial reconstruction algorithm which can be applied to spectra from standard arrays and has provable performance in the presence of both false negative and false positive errors. We also propose a novel design of chips containing universal bases that differs from the one proposed by Preparata et al. (1999). We give a simple algorithm that uses spectra from such chips to reconstruct with high probability random sequences of length lower only by a squared log factor compared to the information theoretic bound. Our algorithm is very robust to errors and has a provable performance even if there are both false negative and false positive errors. Simulations indicate that its sensitivity to errors is also very small in practice.</div></front></TEI><affiliations><list><country><li>États-Unis</li></country><region><li>Californie</li></region></list><tree><noCountry><name sortKey="Halperin, Shay" sort="Halperin, Shay" uniqKey="Halperin S" first="Shay" last="Halperin">Shay Halperin</name><name sortKey="Hartman, Tzvika" sort="Hartman, Tzvika" uniqKey="Hartman T" first="Tzvika" last="Hartman">Tzvika Hartman</name><name sortKey="Shamir, Ron" sort="Shamir, Ron" uniqKey="Shamir R" first="Ron" last="Shamir">Ron Shamir</name></noCountry><country name="États-Unis"><region name="Californie"><name sortKey="Halperin, Eran" sort="Halperin, Eran" uniqKey="Halperin E" first="Eran" last="Halperin">Eran Halperin</name></region></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Sante/explor/MersV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 003215 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 003215 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Sante
|area= MersV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= pubmed:12935339
|texte= Handling long targets and errors in sequencing by hybridization.
}}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/Main/Exploration/RBID.i -Sk "pubmed:12935339" \
| HfdSelect -Kh $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd \
| NlmPubMed2Wicri -a MersV1
| This area was generated with Dilib version V0.6.33. |  |